package topcoder;

public class ShippingCubes {

	public int minimalCost(int N){
		return _minimalCost(N, 1);
	}
	
	private int _minimalCost(int N, int d){
		if(d == 4){
			if(N == 1)
				return 0;
			else
				return Integer.MAX_VALUE;
		}
		else if (N == 1){
			return 1*(4-d);
		}
		else{
			int min = Integer.MAX_VALUE;
			for(int i = N; i > 1; i--){
				if(N % i == 0){
					int c = _minimalCost((int)(N/i), d+1) + i;
					if(c > 0 && c < min)
						min = c;
				}
			}
			return min;
		}
	}
}
